package com.ly.algorithm.DataStructures.problem;

/**
 * @Classname KMP
 * @Description TODO
 * @Date 2020/5/4 14:15
 * @Author 冷心影翼
 */
public class KMP {

    public static void main(String[] args) {
        String str1 ="ABCDADBABCDAB";
        String str2 = "ABCDAB";
        System.out.println(kmpSearch(str1, str2));

    }

    public static int kmpSearch(String str1,String str2) {
        int[] next = kmpNext(str2);
        for(int i=0,j=0;i<str1.length();i++) {
            while (j>0 && str1.charAt(i)!=str2.charAt(j)) {
                j = next[j-1];
            }
            if(str1.charAt(i)==str2.charAt(j)) {
                j++;
            }
            if(j==str2.length()) {
                return i-j+1;
            }
        }
        return -1;
    }

    public static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i=1,j=0;i<dest.length();i++) {
            while (j>0&&dest.charAt(i)!=dest.charAt(j)) {
                next[j] = next[j-1];
            }
            if(dest.charAt(i)==dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return  next;
    }
}


class ViolenceMatch {
    public static void main(String[] args) {
        System.out.println(violenceMatch("ABCDBCDE", "BCcDE"));
    }

    public static int violenceMatch(String s1, String s2) {
        int i=0;
        int j=0;
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        while(i<arr1.length && j<arr2.length) {
            if(arr1[i]==arr2[j]) {
                i++;
                j++;
            }else {
                i=i-(j-1);
                j=0;
            }
        }
        if (j==arr2.length) {
            return i-j;
        }else {
            return -1;
        }
    }
}